import java.util.*;

class Solution {
    // 长度最小的子数组
    public int minSubArrayLen(int target, int[] nums) {
        int len = nums.length;
        int minLen = Integer.MAX_VALUE;
        int sum = 0;
        int left = 0, right = 0;
        while(right < len) {
            sum += nums[right];
            while(sum >= target) {
                minLen = Math.min(minLen, right - left + 1);
                sum -= nums[left++];
            }
            right++;
        }
        System.out.println("left: " + left + " right: " + right + " sum: " + sum);
        minLen = (minLen == Integer.MAX_VALUE) ? 0 : minLen;
        return minLen;
    }

    // 无重复字符的最长子串
    public int lengthOfLongestSubstring(String s) {
        int[] hash = new int[256];
        char[] chs = s.toCharArray();
        int len = chs.length;
        int maxLen = 0;
        for(int left = 0, right = 0; right < len; right++) {
            // 进窗口
            char input = chs[right];
            hash[input]++;
            // 判断
            while(hash[input] > 1) {
                char out = chs[left];
                hash[out]--;
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }
    // 最大连续1的个数III
    public int longestOnes(int[] nums, int k) {
        int len = nums.length;
        int num = 0;
        int maxLen = 0;
        for(int left = 0, right = 0; right < len; right++) {
            if(nums[right] == 0) {
                num++;
            }
            while(num > k) {
                if(nums[left] == 0) {
                    num--;
                }
                left++;
            }
            maxLen = Math.max(maxLen, right - left + 1);
        }
        return maxLen;
    }

    // 将 x 减到 0 的最小操作数
    public int minOperations(int[] nums, int x) {
        // 求连续的最大值
        int len = nums.length;
        int sum = 0;
        // 求中间连续的值
        for(int i = 0; i < len; i++) {
            sum += nums[i];
        }
        x = sum - x;
        if(x < 0) {
            return -1;
        } else if (x == 0) {
            return len;
        }
        sum = 0;
        System.out.println("x: " + x);
        // 中间的最大连续数
        int count = -1;
        for(int left = 0, right = 0; right < len; right++) {
            // 进窗口
            sum += nums[right];
            // 判断
            while (sum > x) {
                // 出窗口
                sum -= nums[left];
                left++;
            }
            // 更新结果
            if (sum == x) {
                count = Math.max(right - left + 1, count);
            }
        }
        count = (count == -1) ? -1 : len - count;
        return count;
    }

    // 最大连续1的个数
    public int findMaxConsecutiveOnes(int[] nums) {
        int len = nums.length;
        int count = 0;
        int maxCount = 0;
        for(int i = 0; i < len; i++) {
            if(nums[i] == 1) {
                count++;
            } else if (nums[i] == 0) {
                maxCount = Math.max(count, maxCount);
                count = 0;
            }
        }
        // 最大数量在最后
        maxCount = Math.max(count, maxCount);
        return maxCount;
    }

    // 水果成篮
    public int totalFruit(int[] fruits) {
        int len = fruits.length;
        int count = 0;
        int[] hash = new int[len];
        int maxSize = 0;
        for(int left = 0, right = 0; right < len; right++) {
            // 进窗口
            // 判断是否是新的水果
            if(hash[fruits[right]] == 0) {
                count++;
            }
            hash[fruits[right]]++;
            // 判断
            while (count > 2) {
                hash[fruits[left]]--;
                if(hash[fruits[left]] == 0) {
                    count--;
                }
                left++;
            }
            // 更新结果
            maxSize = Math.max(maxSize, right - left + 1);
            // System.out.println("left: " + left + " right: " + right + " count: " + count);
        }
        return maxSize;
    }

    // 找到字符串种所有字母异位词
    public List<Integer> findAnagrams(String s, String p) {
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        char[] target = new char[26];
        char[] hash = new char[26];
        int m = pp.length;
        List<Integer> ret = new ArrayList<>();
        for(char ch: pp) {
            target[ch - 'a']++;
        }
        for(int left = 0, right = 0; right < ss.length; right++) {
            // System.out.println("left: " + left + " right: " + right);
            // 进窗口
            int inputIndex = ss[right] - 'a';
            hash[inputIndex]++;
            // 判断
            while (right - left + 1 > m) {
                // 出窗口
                int outIndex = ss[left] - 'a';
                hash[outIndex]--;
                left++;
            }
            // 更新结果
            if(right - left + 1 == m) {
                boolean flag = true;
                for(char ch: pp) {
                    if(hash[ch - 'a'] != target[ch - 'a']) {
                        flag = false;
                        break;
                    }
                }
                if(flag) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }

    // 找到字符串种所有字母异位词 (优化后)
    public List<Integer> findAnagrams2(String s, String p) {
        char[] ss = s.toCharArray();
        char[] pp = p.toCharArray();
        char[] target = new char[26];
        char[] hash = new char[26];
        int m = pp.length;
        List<Integer> ret = new ArrayList<>();
        for(char ch: pp) {
            target[ch - 'a']++;
        }
        for(int left = 0, right = 0, count = 0; right < ss.length; right++) {
            // System.out.println("left: " + left + " right: " + right);
            // 进窗口
            int inputIndex = ss[right] - 'a';
            hash[inputIndex]++;
            if(hash[inputIndex] <= target[inputIndex]) {
                count++;
            }
            // 判断
            while (right - left + 1 > m) {
                // 出窗口
                int outIndex = ss[left] - 'a';
                if(hash[outIndex] <= target[outIndex]) {
                    count--;
                }
                hash[outIndex]--;
                left++;
            }
            // 更新结果
            if(right - left + 1 == m && count == m) {
                ret.add(left);
            }
        }
        return ret;
    }

    // 串联所有单词的子串
    public List<Integer> findSubstring(String s, String[] words) {
        int len = s.length();
        int wordLen = words[0].length();
        int m = words.length;
        List<Integer> ret = new ArrayList<>();
        Map<String, Integer> hash1 = new HashMap<>();
        for(String word: words) {
            hash1.put(word, hash1.getOrDefault(word, 0) + 1);
        }
        for(int i = 0; i < wordLen; i++) {
            Map<String, Integer> hash2 = new HashMap<>();
            for(int left = i, right = i, count = 0; right + wordLen <= len; right += wordLen) {
                // 进窗口 + 维护 count
                String in = s.substring(right, right + wordLen);
                hash2.put(in, hash2.getOrDefault(in, 0) + 1);
                if(hash2.get(in) <= hash1.getOrDefault(in, 0)) {
                    count++;
                }
                // System.out.println("left: " + left + " right: " + right  + " count: " + count + " hash1: " + hash1.getOrDefault(in, 0) + " hash2: " + hash2.get(in));
                // 判断
                if(right - left + 1 > m * wordLen) {
                    String out = s.substring(left, left + wordLen);
                    if(hash2.get(out) <= hash1.getOrDefault(out, 0)) {
                        count--;
                    }
                    hash2.put(out, hash2.get(out) - 1);
                    left += wordLen;
                }
                if(count == m) {
                    ret.add(left);
                }
            }
        }
        return ret;
    }

    // 最小覆盖子串
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();
        int[] hash1 = new int[128];
        int[] hash2 = new int[128];
        int begin = 0;
        int minLen = Integer.MAX_VALUE;
        for(char ch: t) {
            hash1[ch]++;
        }
        for(int left = 0, right = 0, count = 0; right < s.length; right++) {
            // 进窗口
            int in = s[right];
            hash2[in]++;
            // 维护 count
            if(hash2[in] <= hash1[in]) {
                count++;
            }
            // 判断
            while(count >= t.length) {
                // 更新结果
                if(count == t.length && right - left + 1 < minLen) {
                    begin = left;
                    minLen = right - left + 1;
                }
                int out = s[left];
                // 维护 count
                if(hash2[out] <= hash1[out]) {
                    count--;
                }
                // 出窗口
                hash2[out]--;
                left++;
            }
            // System.out.println("left: " + left + " right: " + right + " count " + count);
        }

        // 判断是否有最小覆盖子串
        if(minLen == Integer.MAX_VALUE) {
            return "";
        }
        // 返回结果
        return ss.substring(begin, begin + minLen);
    }
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {1,2,3,4,5};
        solution.minSubArrayLen(11, nums);
    }
}